{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isValidSequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #判断给定的序列是否是二叉树从根到叶的路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二叉树，我们称从根节点到任意叶节点的任意路径中的节点值所构成的序列为该二叉树的一个 &ldquo;<strong>有效序列</strong>&rdquo; 。检查一个给定的序列是否是给定二叉树的一个 &ldquo;<strong>有效序列</strong>&rdquo; 。</p>\n",
    "\n",
    "<p>我们以整数数组 <code>arr</code> 的形式给出这个序列。从根节点到任意叶节点的任意路径中的节点值所构成的序列都是这个二叉树的 &ldquo;<strong>有效序列</strong>&rdquo; 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/12/18/leetcode_testcase_1.png\" style=\"height:250px; width:333px\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,1,0,1]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：\n",
    "</strong>路径 0 -&gt; 1 -&gt; 0 -&gt; 1 是一个&ldquo;有效序列&rdquo;（图中的绿色节点）。\n",
    "其他的&ldquo;有效序列&rdquo;是：\n",
    "0 -&gt; 1 -&gt; 1 -&gt; 0 \n",
    "0 -&gt; 0 -&gt; 0\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/12/18/leetcode_testcase_2.png\" style=\"height:250px; width:333px\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,0,1]\n",
    "<strong>输出：</strong>false \n",
    "<strong>解释：</strong>路径 0 -&gt; 0 -&gt; 1 不存在，所以这不是一个&ldquo;序列&rdquo;。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/12/18/leetcode_testcase_3.png\" style=\"height:250px; width:333px\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,1,1]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>路径 0 -&gt; 1 -&gt; 1 是一个序列，但不是一个&ldquo;有效序列&rdquo;（译者注：因为序列的终点不是叶节点）。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr.length &lt;= 5000</code></li>\n",
    "\t<li><code>0 &lt;= arr[i] &lt;= 9</code></li>\n",
    "\t<li>每个节点的值的取值范围是 <code>[0 - 9]</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [check-if-a-string-is-a-valid-sequence-from-root-to-leaves-path-in-a-binary-tree](https://leetcode.cn/problems/check-if-a-string-is-a-valid-sequence-from-root-to-leaves-path-in-a-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [check-if-a-string-is-a-valid-sequence-from-root-to-leaves-path-in-a-binary-tree](https://leetcode.cn/problems/check-if-a-string-is-a-valid-sequence-from-root-to-leaves-path-in-a-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,1,0,0,1,0,null,null,1,0,0]\\n[0,1,0,1]', '[0,1,0,0,1,0,null,null,1,0,0]\\n[0,0,1]', '[0,1,0,0,1,0,null,null,1,0,0]\\n[0,1,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isValidSequence(self, root: Optional[TreeNode], arr: List[int]) -> bool:\n",
    "        self.res = False \n",
    "\n",
    "        self.traverse(root, arr, [])\n",
    "\n",
    "        return self.res \n",
    "\n",
    "    def traverse(self, root, arr, path):\n",
    "        if root is None or arr == []:\n",
    "            return False \n",
    "\n",
    "        path.append(root.val)\n",
    "\n",
    "        if root.left is None and root.right is None:\n",
    "            if arr == path:\n",
    "                self.res = True\n",
    "\n",
    "        self.traverse(root.left, arr, path)\n",
    "        self.traverse(root.right, arr, path)\n",
    "\n",
    "        path.pop()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isValidSequence(self, root: Optional[TreeNode], arr: List[int]) -> bool:\n",
    "        flag = False \n",
    "\n",
    "        def dfs(node, i):\n",
    "            nonlocal flag \n",
    "\n",
    "            if flag:\n",
    "                return \n",
    "            if not node.left and not node.right:\n",
    "                if i == len(arr) - 1 and node.val == arr[-1]:\n",
    "                    flag = True \n",
    "                return \n",
    "            if i == len(arr) or node.val != arr[i]:\n",
    "                return \n",
    "            if node.left:\n",
    "                dfs(node.left, i + 1)\n",
    "            if node.right:\n",
    "                dfs(node.right, i + 1)\n",
    "\n",
    "        dfs(root, 0)\n",
    "        return flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isValidSequence(self, root: Optional[TreeNode], arr: List[int]) -> bool:\n",
    "        q = [root]\n",
    "        i, n = 0, len(arr)\n",
    "        while q:\n",
    "            nxt = []\n",
    "            for x in q:\n",
    "                if x.val == arr[i]:\n",
    "                    if not x.left and not x.right and i == n-1:\n",
    "                        return True\n",
    "                    if x.left:\n",
    "                        nxt.append(x.left)\n",
    "                    if x.right:\n",
    "                        nxt.append(x.right)\n",
    "            q = nxt\n",
    "            i += 1\n",
    "            if i == n: break\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isValidSequence(self, root: Optional[TreeNode], arr: List[int]) -> bool:\n",
    "        if root is None or arr == []:\n",
    "            return False\n",
    "\n",
    "        if root.left is None and root.right is None:\n",
    "            return [root.val] == arr\n",
    "\n",
    "\n",
    "        cur = arr[0]\n",
    "\n",
    "        if cur != root.val:\n",
    "            return False \n",
    "\n",
    "        return self.isValidSequence(root.left, arr[1:]) \\\n",
    "                or self.isValidSequence(root.right, arr[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isValidSequence(self, root: Optional[TreeNode], arr: List[int]) -> bool:\n",
    "        n = len(arr)\n",
    "\n",
    "        def dfs(root, index):\n",
    "            if index >= n or root is None or root.val != arr[index]:\n",
    "                return False\n",
    "            if root.left is None and root.right is None and root.val == arr[index] and index == n-1:\n",
    "                return True\n",
    "            return dfs(root.left, index+1) or dfs(root.right, index+1)\n",
    "        \n",
    "        return dfs(root, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isValidSequence(self, root: Optional[TreeNode], arr: List[int]) -> bool:\n",
    "        path = []\n",
    "        res = False\n",
    "        def dfs(root):\n",
    "            if not root: return\n",
    "            nonlocal res, path\n",
    "            path.append(root.val)\n",
    "            print(path)\n",
    "            if not root.left and not root.right:\n",
    "                if path == arr:\n",
    "                    res = True\n",
    "\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "            path.pop()\n",
    "        dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isValidSequence(self, root: Optional[TreeNode], arr: List[int]) -> bool:\n",
    "        q = [root]\n",
    "        i, n = 0, len(arr)\n",
    "        while q:\n",
    "            nq = []\n",
    "            for x in q:\n",
    "                if x.val == arr[i]:\n",
    "                    if not x.left and not x.right and i == n-1:\n",
    "                        return True\n",
    "                    if x.left:\n",
    "                        nq.append(x.left)\n",
    "                    if x.right:\n",
    "                        nq.append(x.right)\n",
    "            q = nq\n",
    "            i += 1\n",
    "            if i == n: break\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isValidSequence(self, root: Optional[TreeNode], arr: List[int]) -> bool:\n",
    "        def dfs(root, arr, index):\n",
    "            if index >= len(arr) or root is None or root.val != arr[index]:\n",
    "                return False\n",
    "            if root.left == None and root.right == None and root.val == arr[index] and index == len(arr) -1:\n",
    "                return True\n",
    "            return dfs(root.left, arr, index + 1) or dfs(root.right, arr, index + 1)\n",
    "        return dfs(root, arr, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isValidSequence(self, root: Optional[TreeNode], arr: List[int]) -> bool:\n",
    "        ans=False\n",
    "        def dfs(root,temp):\n",
    "            nonlocal ans\n",
    "            if root==None:\n",
    "                return\n",
    "            if temp==len(arr)-1:\n",
    "                if not root.left and not root.right and root.val==arr[temp]:\n",
    "                    ans=True\n",
    "                return \n",
    "            if root.val==arr[temp]:\n",
    "                if root.left:\n",
    "                    dfs(root.left,temp+1)\n",
    "                if root.right:\n",
    "                    dfs(root.right,temp+1)\n",
    "        dfs(root,0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isValidSequence(self, root: Optional[TreeNode], arr: List[int]) -> bool:\n",
    "        return self.check(root, arr, 0)\n",
    "\n",
    "    def check(self, root, arr, i):\n",
    "        if root is None or i >= len(arr):\n",
    "            return False \n",
    "\n",
    "        if root.left is None and root.right is None:\n",
    "            return arr[i] == root.val and i == len(arr) - 1\n",
    "\n",
    "        if root.val == arr[i]:\n",
    "            return self.check(root.left, arr, i + 1) \\\n",
    "                    or self.check(root.right, arr, i + 1)\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Optional\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def isValidSequence(self, root: Optional[TreeNode], arr: List[int]) -> bool:\n",
    "        def dfs(node, index):\n",
    "            # 如果当前节点为空，或者序列中的当前元素与节点的值不匹配，返回 False\n",
    "            if not node or node.val != arr[index]:\n",
    "                return False\n",
    "            \n",
    "            # 如果已经到达了序列的最后一个元素，检查是否也到达了叶子节点\n",
    "            if index == len(arr) - 1:\n",
    "                return not node.left and not node.right\n",
    "            \n",
    "            # 递归地检查左子树和右子树\n",
    "            return dfs(node.left, index + 1) or dfs(node.right, index + 1)\n",
    "        \n",
    "        return dfs(root, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isValidSequence(self, root: Optional[TreeNode], arr: List[int]) -> bool:\n",
    "        self.res = False \n",
    "\n",
    "        self.traverse(root, arr, [])\n",
    "\n",
    "        return self.res \n",
    "\n",
    "    def traverse(self, root, arr, path):\n",
    "        if root is None or arr == []:\n",
    "            return False \n",
    "\n",
    "        path.append(root.val)\n",
    "\n",
    "        if root.left is None and root.right is None:\n",
    "            if arr == path:\n",
    "                self.res = True\n",
    "\n",
    "        self.traverse(root.left, arr, path)\n",
    "        self.traverse(root.right, arr, path)\n",
    "\n",
    "        path.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isValidSequence(self, root: Optional[TreeNode], arr: List[int]) -> bool:\n",
    "        # 分解问题的思想：利用函数的定义\n",
    "        res = False\n",
    "        def dfs(root, arr, path):\n",
    "            if not root: return False\n",
    "            nonlocal res \n",
    "            if not root.left and not root.right:\n",
    "                path = path + [root.val]\n",
    "                if path == arr:\n",
    "                    res = True\n",
    "            dfs(root.left, arr, path + [root.val])\n",
    "            dfs(root.right, arr, path + [root.val])\n",
    "        dfs(root, arr, [])\n",
    "        return res\n",
    "\n",
    "\n",
    "        # dfs遍历递归的思想\n",
    "        # path = []\n",
    "        # res = False\n",
    "        # def dfs(root):\n",
    "        #     if not root: return\n",
    "        #     nonlocal res, path\n",
    "        #     path.append(root.val)\n",
    "        #     if not root.left and not root.right:\n",
    "        #         if path == arr:\n",
    "        #             res = True\n",
    "\n",
    "        #     dfs(root.left)\n",
    "        #     dfs(root.right)\n",
    "        #     path.pop()\n",
    "        # dfs(root)\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isValidSequence(self, root: Optional[TreeNode], arr: List[int]) -> bool:\n",
    "        n = len(arr)\n",
    "\n",
    "        def dfs(root, index):\n",
    "            if index >= n or root is None or root.val != arr[index]:\n",
    "                return False\n",
    "            if root.left is None and root.right is None and root.val == arr[index] and index == n-1:\n",
    "                return True\n",
    "            return dfs(root.left, index+1) or dfs(root.right, index+1)\n",
    "        \n",
    "        return dfs(root, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isValidSequence(self, root: Optional[TreeNode], arr: List[int]) -> bool:\n",
    "        n = len(arr)\n",
    "\n",
    "        def dfs(root, index):\n",
    "            if index >= n or root is None or root.val != arr[index]:\n",
    "                return False\n",
    "            if root.left is None and root.right is None and root.val == arr[index] and index == n-1:\n",
    "                return True\n",
    "            return dfs(root.left, index+1) or dfs(root.right, index+1)\n",
    "        \n",
    "        return dfs(root, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Optional\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def isValidSequence(self, root: Optional[TreeNode], arr: List[int]) -> bool:\n",
    "        def dfs(node, index):\n",
    "            # 如果当前节点为空，或者序列中的当前元素与节点的值不匹配，返回 False\n",
    "            if not node or node.val != arr[index]:\n",
    "                return False\n",
    "            \n",
    "            # 如果已经到达了序列的最后一个元素，检查是否也到达了叶子节点\n",
    "            if index == len(arr) - 1:\n",
    "                return not node.left and not node.right\n",
    "            \n",
    "            # 递归地检查左子树和右子树\n",
    "            return dfs(node.left, index + 1) or dfs(node.right, index + 1)\n",
    "        \n",
    "        return dfs(root, 0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
